<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.9.0">
    

    

    



    <meta charset="utf-8">
    
    
    
    
    <title>详解Queue的实现方式及其应用 | 欢迎参观小灰灰的网站哟 ヾ(◍°∇°◍)ﾉﾞ ~ | It&#39;s founded on March 9, 2019 and the open source address for the blog notes https://github.com/YUbuntu0109/YUbuntu0109.github.io</title>
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    
    <meta name="theme-color" content="#3F51B5">
    
    
    <meta name="keywords" content="Java,Data Structures and Algorithms">
    <meta name="description" content="学习笔记 : 详解Queue的实现方式及其应用什么是队列队列是一种只能在一端插入( 队尾 ),在另外一端删除( 堆首 )的有序线性表. 队列中第一个插入的元素也是第一个被删除的元素. 所以,队列是一种先进先出( FIFO,First In First Out )或后进后出( LILO,Last In Last Out )线性表. 队列的应用 直接相关的应用   操作系统根据( 具有相同优先级的 )">
<meta name="keywords" content="Java,Data Structures and Algorithms">
<meta property="og:type" content="article">
<meta property="og:title" content="详解Queue的实现方式及其应用">
<meta property="og:url" content="http://yoursite.com/2019/08/31/详解Queue的实现方式及其应用/index.html">
<meta property="og:site_name" content="欢迎参观小灰灰的网站哟 ヾ(◍°∇°◍)ﾉﾞ ~">
<meta property="og:description" content="学习笔记 : 详解Queue的实现方式及其应用什么是队列队列是一种只能在一端插入( 队尾 ),在另外一端删除( 堆首 )的有序线性表. 队列中第一个插入的元素也是第一个被删除的元素. 所以,队列是一种先进先出( FIFO,First In First Out )或后进后出( LILO,Last In Last Out )线性表. 队列的应用 直接相关的应用   操作系统根据( 具有相同优先级的 )">
<meta property="og:locale" content="en">
<meta property="og:updated_time" content="2019-10-31T05:19:50.757Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="详解Queue的实现方式及其应用">
<meta name="twitter:description" content="学习笔记 : 详解Queue的实现方式及其应用什么是队列队列是一种只能在一端插入( 队尾 ),在另外一端删除( 堆首 )的有序线性表. 队列中第一个插入的元素也是第一个被删除的元素. 所以,队列是一种先进先出( FIFO,First In First Out )或后进后出( LILO,Last In Last Out )线性表. 队列的应用 直接相关的应用   操作系统根据( 具有相同优先级的 )">
    
        <link rel="alternate" type="application/atom+xml" title="欢迎参观小灰灰的网站哟 ヾ(◍°∇°◍)ﾉﾞ ~" href="/atom.xml">
    
    <link rel="shortcut icon" href="/favicon.ico">
    <link rel="stylesheet" href="//unpkg.com/hexo-theme-material-indigo@latest/css/style.css">
    <script>window.lazyScripts=[]</script>

    <!-- custom head -->
    

</head>

<body>
    <div id="loading" class="active"></div>

    <aside id="menu" class="hide" >
  <div class="inner flex-row-vertical">
    <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="menu-off">
        <i class="icon icon-lg icon-close"></i>
    </a>
    <div class="brand-wrap" style="background-image:url(/img/brand.jpg)">
      <div class="brand">
        <a href="/" class="avatar waves-effect waves-circle waves-light">
          <img src="/img/my-portrait.jpg">
        </a>
        <hgroup class="introduce">
          <h5 class="nickname">黄宇辉</h5>
          <a href="mailto:3083968068@qq.com" title="3083968068@qq.com" class="mail">3083968068@qq.com</a>
        </hgroup>
      </div>
    </div>
    <div class="scroll-wrap flex-col">
      <ul class="nav">
        
            <li class="waves-block waves-effect">
              <a href="/"  >
                <i class="icon icon-lg icon-home"></i>
                homepage
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/archives"  >
                <i class="icon icon-lg icon-archives"></i>
                Archives
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/tags"  >
                <i class="icon icon-lg icon-tags"></i>
                Tags
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/categories"  >
                <i class="icon icon-lg icon-th-list"></i>
                Categories
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="https://github.com/YUbuntu0109" target="_blank" >
                <i class="icon icon-lg icon-github"></i>
                Github
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="https://github.com/YUbuntu0109" target="_blank" >
                <i class="icon icon-lg icon-weibo"></i>
                Weibo
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/custom"  >
                <i class="icon icon-lg icon-link"></i>
                Test
              </a>
            </li>
        
      </ul>
    </div>
  </div>
</aside>

    <main id="main">
        <header class="top-header" id="header">
    <div class="flex-row">
        <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light on" id="menu-toggle">
          <i class="icon icon-lg icon-navicon"></i>
        </a>
        <div class="flex-col header-title ellipsis">详解Queue的实现方式及其应用</div>
        
        <div class="search-wrap" id="search-wrap">
            <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="back">
                <i class="icon icon-lg icon-chevron-left"></i>
            </a>
            <input type="text" id="key" class="search-input" autocomplete="off" placeholder="Search">
            <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="search">
                <i class="icon icon-lg icon-search"></i>
            </a>
        </div>
        
        
        <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="menuShare">
            <i class="icon icon-lg icon-share-alt"></i>
        </a>
        

        <!-- background music(Mar 11,2019 AM) -->
        <div>
            <iframe frameborder="no" border="0" marginwidth="0" marginheight="0" width=280 height=52 src="//music.163.com/outchain/player?type=2&id=438801642&auto=1&height=32"></iframe>
        </div>
        <!---------------------->
    </div>
</header>
<header class="content-header post-header">

    <div class="container fade-scale">
        <h1 class="title">详解Queue的实现方式及其应用</h1>
        <h5 class="subtitle">
            
                <time datetime="2019-08-31T21:37:20.000Z" itemprop="datePublished" class="page-time">
  2019-08-31
</time>


            
        </h5>
    </div>

    


</header>


<div class="container body-wrap">
    
    <aside class="post-widget">
        <nav class="post-toc-wrap post-toc-shrink" id="post-toc">
            <h4>TOC</h4>
            <ol class="post-toc"><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#学习笔记-详解Queue的实现方式及其应用"><span class="post-toc-number">1.</span> <span class="post-toc-text">学习笔记 : 详解Queue的实现方式及其应用</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#什么是队列"><span class="post-toc-number">1.1.</span> <span class="post-toc-text">什么是队列</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#队列的应用"><span class="post-toc-number">1.2.</span> <span class="post-toc-text">队列的应用</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#队列的实现方式"><span class="post-toc-number">1.3.</span> <span class="post-toc-text">队列的实现方式</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#简单循环数组的实现方法"><span class="post-toc-number">1.3.1.</span> <span class="post-toc-text">简单循环数组的实现方法</span></a></li><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#动态循环数据的实现方法"><span class="post-toc-number">1.3.2.</span> <span class="post-toc-text">动态循环数据的实现方法</span></a></li><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#链表的实现方法"><span class="post-toc-number">1.3.3.</span> <span class="post-toc-text">链表的实现方法</span></a></li></ol></li></ol></li></ol>
        </nav>
    </aside>


<article id="post-详解Queue的实现方式及其应用"
  class="post-article article-type-post fade" itemprop="blogPost">

    <div class="post-card">
        <h1 class="post-card-title">详解Queue的实现方式及其应用</h1>
        <div class="post-meta">
            <time class="post-time" title="2019-08-31 21:37:20" datetime="2019-08-31T21:37:20.000Z"  itemprop="datePublished">2019-08-31</time>

            


            

        </div>
        <div class="post-content" id="post-content" itemprop="postContent">
            <h2 id="学习笔记-详解Queue的实现方式及其应用"><a href="#学习笔记-详解Queue的实现方式及其应用" class="headerlink" title="学习笔记 : 详解Queue的实现方式及其应用"></a>学习笔记 : 详解Queue的实现方式及其应用</h2><h3 id="什么是队列"><a href="#什么是队列" class="headerlink" title="什么是队列"></a>什么是队列</h3><p><em>队列是一种只能在一端插入( 队尾 ),在另外一端删除( 堆首 )的有序线性表. 队列中第一个插入的元素也是第一个被删除的元素. 所以,队列是一种先进先出( FIFO,First In First Out )或后进后出( LILO,Last In Last Out )线性表.</em></p>
<h3 id="队列的应用"><a href="#队列的应用" class="headerlink" title="队列的应用"></a>队列的应用</h3><ol>
<li>直接相关的应用</li>
</ol>
<ul>
<li>操作系统根据( 具有相同优先级的 )任务到达的顺序调度任务( 例如,打印队列 )</li>
<li>模拟现实世界中的队列,如售票柜台前的队伍,或者任何需要先来先服务的场景</li>
<li>多道程序设计</li>
<li>异步数据传输( 文件输入输出,管道,套接字 )</li>
</ul>
<ol start="2">
<li>间接相关的应用</li>
</ol>
<ul>
<li>作为算法的辅助数据结构</li>
<li>其他数据结构的组件</li>
</ul>
<h3 id="队列的实现方式"><a href="#队列的实现方式" class="headerlink" title="队列的实现方式"></a>队列的实现方式</h3><p><em>队列抽象数据类型( 与栈类似 )有多种实现方式,下面是常用的方法 :</em></p>
<ul>
<li>基于简单循环数组的实现方法</li>
<li>基于动态循环数据的实现方法</li>
<li>基于链表的实现方法</li>
</ul>
<h4 id="简单循环数组的实现方法"><a href="#简单循环数组的实现方法" class="headerlink" title="简单循环数组的实现方法"></a>简单循环数组的实现方法</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> pers.huangyuhui.queue;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="keyword">import</span> java.util.Arrays;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@project</span>: Data structures and algorithms</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@description</span>: 基于简单循环数组实现队列</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span>: 黄宇辉</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@date</span>: 8/31/2019-9:59 PM</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span>: 1.0</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@website</span>: https://yubuntu0109.github.io/</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">ArrayQueue</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> front;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> rear;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> capacity;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span>[] array;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">ArrayQueue</span><span class="params">(<span class="keyword">int</span> size)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.capacity = size;</span><br><span class="line">        front = rear = -<span class="number">1</span>;</span><br><span class="line">        array = <span class="keyword">new</span> <span class="keyword">int</span>[size];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> ArrayQueue <span class="title">createQueue</span><span class="params">(<span class="keyword">int</span> size)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> ArrayQueue(size);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isEmpty</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> (front == -<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isFull</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> ((rear + <span class="number">1</span>) % capacity == front);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">traverse</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        System.out.println(Arrays.toString(array));</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getQueueSize</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (front == -<span class="number">1</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">int</span> size = (capacity - front + rear + <span class="number">1</span>) % capacity;</span><br><span class="line">        <span class="keyword">if</span> (size == <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> capacity;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="keyword">return</span> size;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//入队</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">enQueue</span><span class="params">(<span class="keyword">int</span> data)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (isFull()) &#123;</span><br><span class="line">            System.err.println(<span class="string">"error : the queue is overflow"</span>);</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            rear = (rear + <span class="number">1</span>) % capacity;</span><br><span class="line">            array[rear] = data;</span><br><span class="line">            <span class="keyword">if</span> (front == -<span class="number">1</span>) &#123;</span><br><span class="line">                front = rear;</span><br><span class="line">            &#125;</span><br><span class="line">            System.out.println(<span class="string">"enter the data into the queue successfully : "</span> + data);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//出队</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">deQueue</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> data = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">if</span> (isEmpty()) &#123;</span><br><span class="line">            System.err.println(<span class="string">"error : the queue is empty"</span>);</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            data = array[front];</span><br><span class="line">            array[front] = <span class="number">0</span>;</span><br><span class="line">            <span class="keyword">if</span> (front == rear) &#123;</span><br><span class="line">                front = rear = -<span class="number">1</span>;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                front = (front + <span class="number">1</span>) % capacity;</span><br><span class="line">            &#125;</span><br><span class="line">            System.out.println(<span class="string">"delete the data from the queue successfully : "</span> + data);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> data;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//test</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</span><br><span class="line">        ArrayQueue queue = ArrayQueue.createQueue(<span class="number">5</span>);</span><br><span class="line">        <span class="comment">//enter</span></span><br><span class="line">        queue.enQueue(<span class="number">1</span>);</span><br><span class="line">        queue.enQueue(<span class="number">2</span>);</span><br><span class="line">        queue.enQueue(<span class="number">3</span>);</span><br><span class="line">        queue.enQueue(<span class="number">4</span>);</span><br><span class="line">        queue.enQueue(<span class="number">5</span>);</span><br><span class="line">        System.out.println(<span class="string">"the size of queue : "</span> + queue.getQueueSize());</span><br><span class="line">        System.out.print(<span class="string">"traverse the queue : "</span>);</span><br><span class="line">        queue.traverse();</span><br><span class="line">        <span class="comment">//delete</span></span><br><span class="line">        queue.deQueue();</span><br><span class="line">        queue.deQueue();</span><br><span class="line">        queue.deQueue();</span><br><span class="line">        queue.deQueue();</span><br><span class="line">        queue.deQueue();</span><br><span class="line">        System.out.println(<span class="string">"the size of queue : "</span> + queue.getQueueSize());</span><br><span class="line">        System.out.print(<span class="string">"traverse the queue : "</span>);</span><br><span class="line">        queue.traverse();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><em>程序运行结果如下 :</em><br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line">enter the data into the queue successfully : <span class="number">1</span></span><br><span class="line">enter the data into the queue successfully : <span class="number">2</span></span><br><span class="line">enter the data into the queue successfully : <span class="number">3</span></span><br><span class="line">enter the data into the queue successfully : <span class="number">4</span></span><br><span class="line">enter the data into the queue successfully : <span class="number">5</span></span><br><span class="line">the size of queue : <span class="number">5</span></span><br><span class="line">traverse the queue : [<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">4</span>, <span class="number">5</span>]</span><br><span class="line"></span><br><span class="line">delete the data from the queue successfully : <span class="number">1</span></span><br><span class="line">delete the data from the queue successfully : <span class="number">2</span></span><br><span class="line">delete the data from the queue successfully : <span class="number">3</span></span><br><span class="line">delete the data from the queue successfully : <span class="number">4</span></span><br><span class="line">delete the data from the queue successfully : <span class="number">5</span></span><br><span class="line">the size of queue : <span class="number">0</span></span><br><span class="line">traverse the queue : [<span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>]</span><br></pre></td></tr></table></figure></p>
<h4 id="动态循环数据的实现方法"><a href="#动态循环数据的实现方法" class="headerlink" title="动态循环数据的实现方法"></a>动态循环数据的实现方法</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> pers.huangyuhui.queue;</span><br><span class="line"></span><br><span class="line"><span class="keyword">import</span> java.util.Arrays;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@project</span>: Data structures and algorithms</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@description</span>: 基于动态循环数组实现队列</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span>: 黄宇辉</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@date</span>: 9/1/2019-8:59 AM</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span>: 1.0</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@website</span>: https://yubuntu0109.github.io/</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">DynArrayQueue</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> front;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> rear;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> capacity;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span>[] array;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="title">DynArrayQueue</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        capacity = <span class="number">1</span>;</span><br><span class="line">        front = rear = -<span class="number">1</span>;</span><br><span class="line">        array = <span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">1</span>];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> DynArrayQueue <span class="title">createDynArrayQueue</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> DynArrayQueue();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isEmpty</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> (front == -<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isFull</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> ((rear + <span class="number">1</span>) % capacity == front);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">traverse</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        System.out.println(Arrays.toString(array));</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getQueueSize</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (front == -<span class="number">1</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">int</span> size = (capacity - front + rear + <span class="number">1</span>) % capacity;</span><br><span class="line">        <span class="keyword">if</span> (size == <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> capacity;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="keyword">return</span> size;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">//扩容</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">resizeQueue</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> initCapacity = capacity;</span><br><span class="line">        capacity *= <span class="number">2</span>;</span><br><span class="line">        <span class="keyword">int</span>[] oldArray = array;</span><br><span class="line">        array = <span class="keyword">new</span> <span class="keyword">int</span>[<span class="keyword">this</span>.capacity];</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; oldArray.length; i++) &#123;</span><br><span class="line">            array[i] = oldArray[i];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//important</span></span><br><span class="line">        <span class="keyword">if</span> (rear &lt; front) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; front; i++) &#123;</span><br><span class="line">                array[i + initCapacity] = <span class="keyword">this</span>.array[i];</span><br><span class="line">                array[i] = <span class="number">0</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            rear += initCapacity;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//入队</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">enQueue</span><span class="params">(<span class="keyword">int</span> data)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (isFull()) &#123;</span><br><span class="line">            resizeQueue();</span><br><span class="line">        &#125;</span><br><span class="line">        rear = (rear + <span class="number">1</span>) % capacity;</span><br><span class="line">        array[rear] = data;</span><br><span class="line">        <span class="keyword">if</span> (front == -<span class="number">1</span>) &#123;</span><br><span class="line">            front = rear;</span><br><span class="line">        &#125;</span><br><span class="line">        System.out.println(<span class="string">"enter a data into the queue successfully : "</span> + data);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//出队</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">deQueue</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> data = -<span class="number">1</span>;</span><br><span class="line">        <span class="keyword">if</span> (isEmpty()) &#123;</span><br><span class="line">            System.err.println(<span class="string">"error : the queue is empty"</span>);</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            data = array[front];</span><br><span class="line">            array[front] = <span class="number">0</span>; <span class="comment">//delete the data</span></span><br><span class="line">            <span class="keyword">if</span> (front == rear) &#123;</span><br><span class="line">                front = rear = -<span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                front = (front + <span class="number">1</span>) % capacity;</span><br><span class="line">            &#125;</span><br><span class="line">            System.out.println(<span class="string">"delete a data from the queue successfully : "</span> + data);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> data;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">//test</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</span><br><span class="line">        DynArrayQueue dynArrayQueue = DynArrayQueue.createDynArrayQueue();</span><br><span class="line">        <span class="comment">//enter</span></span><br><span class="line">        dynArrayQueue.enQueue(<span class="number">1</span>);</span><br><span class="line">        dynArrayQueue.enQueue(<span class="number">2</span>);</span><br><span class="line">        dynArrayQueue.enQueue(<span class="number">3</span>);</span><br><span class="line">        dynArrayQueue.enQueue(<span class="number">4</span>);</span><br><span class="line">        dynArrayQueue.enQueue(<span class="number">5</span>);</span><br><span class="line">        System.out.println(<span class="string">"the size of queue : "</span> + dynArrayQueue.getQueueSize());</span><br><span class="line">        System.out.print(<span class="string">"traverse the queue : "</span>);</span><br><span class="line">        dynArrayQueue.traverse();</span><br><span class="line">        <span class="comment">//delete</span></span><br><span class="line">        dynArrayQueue.deQueue();</span><br><span class="line">        dynArrayQueue.deQueue();</span><br><span class="line">        dynArrayQueue.deQueue();</span><br><span class="line">        dynArrayQueue.deQueue();</span><br><span class="line">        dynArrayQueue.deQueue();</span><br><span class="line">        System.out.println(<span class="string">"the size of queue : "</span> + dynArrayQueue.getQueueSize());</span><br><span class="line">        System.out.print(<span class="string">"traverse the queue : "</span>);</span><br><span class="line">        dynArrayQueue.traverse();</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><em>程序运行结果如下所示 :</em><br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line">enter a data into the queue successfully : <span class="number">1</span></span><br><span class="line">enter a data into the queue successfully : <span class="number">2</span></span><br><span class="line">enter a data into the queue successfully : <span class="number">3</span></span><br><span class="line">enter a data into the queue successfully : <span class="number">4</span></span><br><span class="line">enter a data into the queue successfully : <span class="number">5</span></span><br><span class="line">the size of queue : <span class="number">5</span></span><br><span class="line">traverse the queue : [<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">4</span>, <span class="number">5</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>]</span><br><span class="line"></span><br><span class="line">delete a data from the queue successfully : <span class="number">1</span></span><br><span class="line">delete a data from the queue successfully : <span class="number">2</span></span><br><span class="line">delete a data from the queue successfully : <span class="number">3</span></span><br><span class="line">delete a data from the queue successfully : <span class="number">4</span></span><br><span class="line">delete a data from the queue successfully : <span class="number">5</span></span><br><span class="line">the size of queue : <span class="number">0</span></span><br><span class="line">traverse the queue : [<span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>]</span><br></pre></td></tr></table></figure></p>
<h4 id="链表的实现方法"><a href="#链表的实现方法" class="headerlink" title="链表的实现方法"></a>链表的实现方法</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> pers.huangyuhui.queue;</span><br><span class="line"></span><br><span class="line"><span class="comment">//定义一个单向链表</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">LLNode</span> </span>&#123;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> data;</span><br><span class="line">    <span class="keyword">private</span> LLNode next;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">LLNode</span><span class="params">(<span class="keyword">int</span> data)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.data = data;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getData</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> data;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">setData</span><span class="params">(<span class="keyword">int</span> data)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.data = data;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> LLNode <span class="title">getNext</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> next;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">setNext</span><span class="params">(LLNode next)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.next = next;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@project</span>: Data structures and algorithms</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@description</span>: 基于链表实现队列</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span>: 黄宇辉</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@date</span>: 9/1/2019-9:19 AM</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span>: 1.0</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@website</span>: https://yubuntu0109.github.io/</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">LLQueue</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> LLNode frontNode; <span class="comment">//represents headNode</span></span><br><span class="line">    <span class="keyword">private</span> LLNode rearNode; <span class="comment">//represents lastNode</span></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">LLQueue</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.frontNode = <span class="keyword">null</span>;</span><br><span class="line">        <span class="keyword">this</span>.rearNode = <span class="keyword">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> LLQueue <span class="title">createQueue</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> LLQueue();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isEmpty</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> (frontNode == <span class="keyword">null</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getQueueSize</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> length = <span class="number">0</span>;</span><br><span class="line">        LLNode currentNode = frontNode;</span><br><span class="line">        <span class="keyword">while</span> (currentNode != <span class="keyword">null</span>) &#123;</span><br><span class="line">            length++;</span><br><span class="line">            currentNode = currentNode.getNext();</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> length;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//遍历</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">traverse</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (isEmpty()) &#123;</span><br><span class="line">            System.err.println(<span class="string">"error : the queue is empty !"</span>);</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        LLNode currentNode = frontNode;</span><br><span class="line">        System.out.print(<span class="string">"the all data of queue : [ "</span>);</span><br><span class="line">        <span class="keyword">while</span> (currentNode != <span class="keyword">null</span>) &#123;</span><br><span class="line">            System.out.print(currentNode.getData() + <span class="string">" ,"</span>);</span><br><span class="line">            currentNode = currentNode.getNext();</span><br><span class="line">        &#125;</span><br><span class="line">        System.out.print(<span class="string">" ]\n"</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//入队</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">enQueue</span><span class="params">(<span class="keyword">int</span> data)</span> </span>&#123;</span><br><span class="line">        LLNode newNode = <span class="keyword">new</span> LLNode(data);</span><br><span class="line">        <span class="keyword">if</span> (rearNode != <span class="keyword">null</span>) &#123;</span><br><span class="line">            rearNode.setNext(newNode);</span><br><span class="line">        &#125;</span><br><span class="line">        rearNode = newNode;</span><br><span class="line">        <span class="keyword">if</span> (frontNode == <span class="keyword">null</span>) &#123;</span><br><span class="line">            frontNode = rearNode;</span><br><span class="line">        &#125;</span><br><span class="line">        System.out.println(<span class="string">"enter the data into the queue successfully : "</span> + data);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//出队</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">deQueue</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> data = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">if</span> (isEmpty()) &#123;</span><br><span class="line">            System.err.println(<span class="string">"error : the queue is empty"</span>);</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            data = frontNode.getData();</span><br><span class="line">            frontNode = frontNode.getNext();</span><br><span class="line">        &#125;</span><br><span class="line">        System.out.println(<span class="string">"delete the data from the queue successfully : "</span> + data);</span><br><span class="line">        <span class="keyword">return</span> data;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">//test</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</span><br><span class="line">        LLQueue queue = LLQueue.createQueue();</span><br><span class="line">        <span class="comment">//enter</span></span><br><span class="line">        queue.enQueue(<span class="number">1</span>);</span><br><span class="line">        queue.enQueue(<span class="number">2</span>);</span><br><span class="line">        queue.enQueue(<span class="number">3</span>);</span><br><span class="line">        queue.enQueue(<span class="number">4</span>);</span><br><span class="line">        queue.enQueue(<span class="number">5</span>);</span><br><span class="line">        System.out.println(<span class="string">"the size of the queue : "</span> + queue.getQueueSize());</span><br><span class="line">        System.out.print(<span class="string">"traverse the queue : "</span>);</span><br><span class="line">        queue.traverse();</span><br><span class="line">        <span class="comment">//delete</span></span><br><span class="line">        queue.deQueue();</span><br><span class="line">        queue.deQueue();</span><br><span class="line">        queue.deQueue();</span><br><span class="line">        queue.deQueue();</span><br><span class="line">        queue.deQueue();</span><br><span class="line">        System.out.println(<span class="string">"the size of the queue : "</span> + queue.getQueueSize());</span><br><span class="line">        System.out.print(<span class="string">"traverse the queue : "</span>);</span><br><span class="line">        queue.traverse();</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><em>程序运行结果如下所示 :</em><br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line">enter the data into the queue successfully : <span class="number">1</span></span><br><span class="line">enter the data into the queue successfully : <span class="number">2</span></span><br><span class="line">enter the data into the queue successfully : <span class="number">3</span></span><br><span class="line">enter the data into the queue successfully : <span class="number">4</span></span><br><span class="line">enter the data into the queue successfully : <span class="number">5</span></span><br><span class="line">the size of the queue : <span class="number">5</span></span><br><span class="line">traverse the queue : the all data of queue : [ <span class="number">1</span> ,<span class="number">2</span> ,<span class="number">3</span> ,<span class="number">4</span> ,<span class="number">5</span> , ]</span><br><span class="line"></span><br><span class="line">delete the data from the queue successfully : <span class="number">1</span></span><br><span class="line">delete the data from the queue successfully : <span class="number">2</span></span><br><span class="line">delete the data from the queue successfully : <span class="number">3</span></span><br><span class="line">delete the data from the queue successfully : <span class="number">4</span></span><br><span class="line">delete the data from the queue successfully : <span class="number">5</span></span><br><span class="line">the size of the queue : <span class="number">0</span></span><br><span class="line">traverse the queue : error : the queue is empty !</span><br></pre></td></tr></table></figure></p>
<p><em>参考书籍( 已纠正书中错误的示例代码 ) : 《数据结构与算法经典问题解析 - 原书第2版》</em></p>

        </div>

        <blockquote class="post-copyright">
    
    <div class="content">
        
<span class="post-time">
    Last updated: <time datetime="2019-10-31T05:19:50.757Z" itemprop="dateUpdated">2019-10-31 05:19:50</time>
</span><br>


        
    </div>
    
    <footer>
        <a href="http://yoursite.com">
            <img src="/img/my-portrait.jpg" alt="黄宇辉">
            黄宇辉
        </a>
    </footer>
</blockquote>

        
<div class="page-reward">
    <a id="rewardBtn" href="javascript:;" class="page-reward-btn waves-effect waves-circle waves-light">赏</a>
</div>



        <div class="post-footer">
            
	<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/Data-Structures-and-Algorithms/">Data Structures and Algorithms</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/Java/">Java</a></li></ul>


            
<div class="page-share-wrap">
    

<div class="page-share" id="pageShare">
    <ul class="reset share-icons">
      <li>
        <a class="weibo share-sns" target="_blank" href="http://service.weibo.com/share/share.php?url=http://yoursite.com/2019/08/31/详解Queue的实现方式及其应用/&title=《详解Queue的实现方式及其应用》 — 欢迎参观小灰灰的网站哟 ヾ(◍°∇°◍)ﾉﾞ ~&pic=http://yoursite.com/img/my-portrait.jpg" data-title="微博">
          <i class="icon icon-weibo"></i>
        </a>
      </li>
      <li>
        <a class="weixin share-sns wxFab" href="javascript:;" data-title="微信">
          <i class="icon icon-weixin"></i>
        </a>
      </li>
      <li>
        <a class="qq share-sns" target="_blank" href="http://connect.qq.com/widget/shareqq/index.html?url=http://yoursite.com/2019/08/31/详解Queue的实现方式及其应用/&title=《详解Queue的实现方式及其应用》 — 欢迎参观小灰灰的网站哟 ヾ(◍°∇°◍)ﾉﾞ ~&source=My Personal Website For Blog" data-title=" QQ">
          <i class="icon icon-qq"></i>
        </a>
      </li>
      <li>
        <a class="facebook share-sns" target="_blank" href="https://www.facebook.com/sharer/sharer.php?u=http://yoursite.com/2019/08/31/详解Queue的实现方式及其应用/" data-title=" Facebook">
          <i class="icon icon-facebook"></i>
        </a>
      </li>
      <li>
        <a class="twitter share-sns" target="_blank" href="https://twitter.com/intent/tweet?text=《详解Queue的实现方式及其应用》 — 欢迎参观小灰灰的网站哟 ヾ(◍°∇°◍)ﾉﾞ ~&url=http://yoursite.com/2019/08/31/详解Queue的实现方式及其应用/&via=http://yoursite.com" data-title=" Twitter">
          <i class="icon icon-twitter"></i>
        </a>
      </li>
      <li>
        <a class="google share-sns" target="_blank" href="https://plus.google.com/share?url=http://yoursite.com/2019/08/31/详解Queue的实现方式及其应用/" data-title=" Google+">
          <i class="icon icon-google-plus"></i>
        </a>
      </li>
    </ul>
 </div>



    <a href="javascript:;" id="shareFab" class="page-share-fab waves-effect waves-circle">
        <i class="icon icon-share-alt icon-lg"></i>
    </a>
</div>



        </div>
    </div>

    
<nav class="post-nav flex-row flex-justify-between">
  
    <div class="waves-block waves-effect prev">
      <a href="/2019/09/01/详解Binary-Tree的实现方式及其应用/" id="post-prev" class="post-nav-link">
        <div class="tips"><i class="icon icon-angle-left icon-lg icon-pr"></i> Prev</div>
        <h4 class="title">详解Binary Tree的实现方式及其应用</h4>
      </a>
    </div>
  

  
    <div class="waves-block waves-effect next">
      <a href="/2019/08/31/软件工程琐碎知识点/" id="post-next" class="post-nav-link">
        <div class="tips">Next <i class="icon icon-angle-right icon-lg icon-pl"></i></div>
        <h4 class="title">软件工程琐碎知识点</h4>
      </a>
    </div>
  
</nav>



    




















</article>

<div id="reward" class="page-modal reward-lay">
    <a class="close" href="javascript:;"><i class="icon icon-close"></i></a>
    <h3 class="reward-title">
        <i class="icon icon-quote-left"></i>
        thanks ~
        <i class="icon icon-quote-right"></i>
    </h3>
    <div class="reward-content">
        
        <div class="reward-code">
            <img id="rewardCode" src="/img/Wechat_appreciates.png" alt="打赏二维码">
        </div>
        
    </div>
</div>



</div>

        <footer class="footer">
    <div class="top">
        

        <p>
            
                <span><a href="/atom.xml" target="_blank" class="rss" title="rss"><i class="icon icon-lg icon-rss"></i></a></span>
            
            <span>This blog is licensed under a <a rel="license" href="https://creativecommons.org/licenses/by/4.0/">Creative Commons Attribution 4.0 International License</a>.</span>
        </p>
    </div>
    <div class="bottom">
        <!-- 统计网站用户访问量. 技术支持：不蒜子(http://busuanzi.ibruce.info/) ————> Mar 13,2019 -->
        <p>
            <font style='font-size: 12px;color:springgreen'>
                    <div align="center">
                        <!-- 安装脚本 -->
                        <script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
                        <!-- 安装标签 -->
                        <span id="busuanzi_container_site_pv">
                            ◎用户总访问量 : <span id="busuanzi_value_site_pv"></span> 次 ~ &nbsp&nbsp
                        </span>
                        <span id="busuanzi_container_site_uv">
                            ◎总访客数(（づ￣3￣）づ╭❤～) : <span id="busuanzi_value_site_uv"></span>人 ~
                        </span>
                    </div>
                </font>
            </p>
            <!---------->
            <p>
                <font style='font-size: 10px'>
                    <span>黄宇辉 &copy; 2019</span>
                    <span>
                        
                        Blog source <a href="https://github.com/YUbuntu0109/YUbuntu0109.github.io" target="_blank">Github</a> 
                        Power by <a href="http://hexo.io/" target="_blank">Hexo</a>
                        Theme <a href="https://github.com/yscoder/hexo-theme-indigo" target="_blank">indigo</a>
                    </span>
                </font>
            </p>
        </div>
    </footer>
    </main>
    <div class="mask" id="mask"></div>
<a href="javascript:;" id="gotop" class="waves-effect waves-circle waves-light"><span class="icon icon-lg icon-chevron-up"></span></a>



<div class="global-share" id="globalShare">
    <ul class="reset share-icons">
      <li>
        <a class="weibo share-sns" target="_blank" href="http://service.weibo.com/share/share.php?url=http://yoursite.com/2019/08/31/详解Queue的实现方式及其应用/&title=《详解Queue的实现方式及其应用》 — 欢迎参观小灰灰的网站哟 ヾ(◍°∇°◍)ﾉﾞ ~&pic=http://yoursite.com/img/my-portrait.jpg" data-title="微博">
          <i class="icon icon-weibo"></i>
        </a>
      </li>
      <li>
        <a class="weixin share-sns wxFab" href="javascript:;" data-title="微信">
          <i class="icon icon-weixin"></i>
        </a>
      </li>
      <li>
        <a class="qq share-sns" target="_blank" href="http://connect.qq.com/widget/shareqq/index.html?url=http://yoursite.com/2019/08/31/详解Queue的实现方式及其应用/&title=《详解Queue的实现方式及其应用》 — 欢迎参观小灰灰的网站哟 ヾ(◍°∇°◍)ﾉﾞ ~&source=My Personal Website For Blog" data-title=" QQ">
          <i class="icon icon-qq"></i>
        </a>
      </li>
      <li>
        <a class="facebook share-sns" target="_blank" href="https://www.facebook.com/sharer/sharer.php?u=http://yoursite.com/2019/08/31/详解Queue的实现方式及其应用/" data-title=" Facebook">
          <i class="icon icon-facebook"></i>
        </a>
      </li>
      <li>
        <a class="twitter share-sns" target="_blank" href="https://twitter.com/intent/tweet?text=《详解Queue的实现方式及其应用》 — 欢迎参观小灰灰的网站哟 ヾ(◍°∇°◍)ﾉﾞ ~&url=http://yoursite.com/2019/08/31/详解Queue的实现方式及其应用/&via=http://yoursite.com" data-title=" Twitter">
          <i class="icon icon-twitter"></i>
        </a>
      </li>
      <li>
        <a class="google share-sns" target="_blank" href="https://plus.google.com/share?url=http://yoursite.com/2019/08/31/详解Queue的实现方式及其应用/" data-title=" Google+">
          <i class="icon icon-google-plus"></i>
        </a>
      </li>
    </ul>
 </div>


<div class="page-modal wx-share" id="wxShare">
    <a class="close" href="javascript:;"><i class="icon icon-close"></i></a>
    <p>扫一扫，分享到微信</p>
    <img src="//api.qrserver.com/v1/create-qr-code/?data=http://yoursite.com/2019/08/31/详解Queue的实现方式及其应用/" alt="微信分享二维码">
</div>




    <script src="//cdn.bootcss.com/node-waves/0.7.4/waves.min.js"></script>
<script>
var BLOG = { ROOT: '/', SHARE: true, REWARD: true };


</script>

<script src="//unpkg.com/hexo-theme-material-indigo@latest/js/main.min.js"></script>


<div class="search-panel" id="search-panel">
    <ul class="search-result" id="search-result"></ul>
</div>
<template id="search-tpl">
<li class="item">
    <a href="{path}" class="waves-block waves-effect">
        <div class="title ellipsis" title="{title}">{title}</div>
        <div class="flex-row flex-middle">
            <div class="tags ellipsis">
                {tags}
            </div>
            <time class="flex-col time">{date}</time>
        </div>
    </a>
</li>
</template>

<script src="//unpkg.com/hexo-theme-material-indigo@latest/js/search.min.js" async></script>








<script>
(function() {
    var OriginTitile = document.title, titleTime;
    document.addEventListener('visibilitychange', function() {
        if (document.hidden) {
            document.title = 'Where are you going ?';
            clearTimeout(titleTime);
        } else {
            document.title = 'As long as you love me ~';
            titleTime = setTimeout(function() {
                document.title = OriginTitile;
            },2000);
        }
    });
})();
</script>



</body>
</html>
